package org.hot100.h139;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author yu
 * @Date 2021/12/31
 */
public class Solution {

    public static void main(String[] args) {

        String s = "catsandog";

        List<String> list = new ArrayList<>();
        list.add("cats");
        list.add("dog");
        list.add("sand");
        list.add("and");
        list.add("cat");

        Solution solution = new Solution();
        System.out.println(solution.wordBreak(s, list));

    }

    public boolean wordBreak(String s, List<String> wordDict) {
/*        boolean[] dp = new boolean[s.length() + 1];

        dp[0] = true;   //没有具体的数值意义，仅仅是为了递推公式

        // 外层遍历背包——字符串s
        for(int i = 1; i <= s.length(); i++){
            // 内层遍历物品，就是字典中的元素（如果物品的排序顺序（{1,5} ≠ {5,1），就可以采用物品内循环的排列解法）
            for(int j = 0; j < i; j++){ // j要小于等于i,控制substring的边界
                if(wordDict.contains(s.substring(j,i)) && dp[j]){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.length()];*/

        boolean[] flag = new boolean[s.length() + 1];

        flag[0] = true;
        for (int i = 0; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (wordDict.contains(s.substring(j, i)) && flag[j]) {
                    flag[i] = true;
                    break;
                }
            }

        }

        return flag[s.length()];
    }

}
